34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置
分析
非递减顺序的意思是升序但是可能存在重复元素，
思路是用一个二分法找左边界，再写一个二分法找右边界，重点是如何通过二分法查找单个边界，
其实方式很简单，以查找右边界为例，还是通过二分法来查找，获取区间的中间元素的时候，如果中间元素大于目标值，就更新右区间，其余所有情况都更新左区间，这里跟经典的二分查找的区别是，经典的二分法写法是遇到目标值就跳出循环，但是这里是查找右边界，因此遇到目标元素依然更新左区间，继续收缩区间，同时记录一下当前 mid 为右边界值，这样的话，因为没有遇到某个值跳出循环的条件（老的二分法就是这样的），因此最终一定会扫描到右边界所在的值，最终跳出循环，上一个循环记录的边界值，就是最终的边界。
有的时候会想会不会跳过了最终边界，答案是不会，例如 5 5 5 8 10 12 14 15，假设当前区间是 [0,7] 目标是是 5 ，中间索引是 3，值是 8 ，中间索引的值小于目标值，更新右区间为 3-1，也就是 2，因此这样最终还是会找到右边界。
为什么不会，究其原因，主要因为数列是有序的，而且在每一次循环中，我们都在不断更新区间的左右边界，因此，只要我们对左右边界的定义不变，更新左右边界时的操作不出问题，那么在最终跳出循环的时候，我们就能按照我们设定好的方式，遍历完序列中所有的值，二分法的实际效果就是，即使只挑选几个值（每次区间的 mid 值），也能保证不遗漏。二分查找的本质，就是有序数列的一种快速遍历方式。
左边界同理。
常规的二分法有三个变量，查询区间
[start,end]和 区间中间索引值 mid，但是查找边界的二分法有第四个变量，边界 border。 而且常规的二分法以 mid 为最终值，但是查找边界的时候，border 值才是最终返回的值，二分法只是为了快速遍历。为什么二分法能快速遍历，因为数组有序。
public int[] searchRange(int[] nums, int target) {
int leftBorder = binarySearchFromLeft(nums,target);
int rightBorder = binarySearchFromRight(nums,target);
return new int[]{leftBorder,rightBorder};
}
public int binarySearchFromRight(int[] nums,int target){
int start=0, end = nums.length-1;
int rightBorder = -1;
while(start<=end){
int mid = start+(end-start)/2;
if (nums[mid]>target){
// 从右侧确定右边界
end = mid-1;
} else {
start = mid+1;
if(nums[mid]==target){
rightBorder = mid;
}
}
}
return rightBorder;
}
public int binarySearchFromLeft(int[] nums,int target){
int start=0, end = nums.length-1;
int leftBorder = -1;
while(start<=end){
int mid = start+(end-start)/2;
if (nums[mid]<target){
// 从左侧确定左边界
start = mid+1;
} else {
end = mid-1;
if(nums[mid]==target){
leftBorder = mid;
}
}
}
return leftBorder;
}
解题
通过这个题，我们对二分法的的使用应该有一个更深层次的理解，二分法本质上是一种从有序数组两侧快速往中间逼近的方法，可以有效加快逼近的速度，而且不会遗漏元素。
而且这个题也让我们明白，只要是有序数组，不管有没有重复元素，都可以用二分法